package com.example.mykotlinapp.test

/**
 *给定一个不含重复单词的列表，编写一个程序，返回给定单词列表中所有的连接词。

连接词的定义为：一个字符串完全是由至少两个给定数组中的单词组成的。

示例:

输入: ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]

输出: ["catsdogcats","dogcatsdog","ratcatdogcat"]

解释: "catsdogcats"由"cats", "dog" 和 "cats"组成;
"dogcatsdog"由"dog", "cats"和"dog"组成;
"ratcatdogcat"由"rat", "cat", "dog"和"cat"组成。
说明:

给定数组的元素总数不超过 10000。
给定数组中元素的长度总和不超过 600000。
所有输入字符串只包含小写字母。
不需要考虑答案输出的顺序。
 *
 * @author zhudeshuai
 * @since 2019/8/14
 */


fun findAllConcatenatedWordsInADict(words: Array<String>): List<String> {
    val result = mutableListOf<String>()
    //数据分组
    val map = mutableMapOf<Char, MutableList<String>>()
    for (i in 0 until words.size) {
        var arrayList = map[words[i][0]]
        if (arrayList == null) {
            arrayList = mutableListOf()
            map[words[i][0]] = arrayList
        }
        arrayList.add(words[i])
    }
    words.forEach {
        loop(map, it, ArrayList(), result)
    }
    return result
}

fun loop(
    map: Map<Char, MutableList<String>>,
    originalStr: String,//原有数据
    targetStr: List<String>,
    result: MutableList<String>
) {
    if (targetStr.isEmpty()) {
        val arrayList = map[originalStr[0]]?.filter {
            originalStr != it
        }
        if (arrayList != null) {
            loop(map, originalStr, arrayList, result)
        }

    } else {
        targetStr.forEach {
            val targetList = ArrayList<String>()
            val arrayList = map[it[0]]
            if (arrayList != null) {
                arrayList.forEach { itemStr ->
                    if (it.contains(itemStr)) {
                        if (it == itemStr) {
                            result.add(originalStr)
                            return
                        }
                        val startIndex = it.indexOf(itemStr)
                        targetList.add(it.removeRange(startIndex, startIndex + itemStr.length))
                    }
                }
                loop(map, it, targetList, result)
            }

        }
    }


}

fun main() {
    val target = arrayOf("cat", "cats", "catsdogcats", "dog", "dogcatsdog", "hippopotamuses", "rat", "ratcatdogcat")
    println(findAllConcatenatedWordsInADict(target))
}